Search for: All records

We prove that the most natural low-degree test for polynomials over finite fields is “robust” in the high-error regime for linear-sized fields. Specifically we consider the “local” agreement of a function $$f:\mathbb{F}_{q}^{m}\rightarrow \mathbb{F}_{q}$$ from the space of degree-d polynomials, i.e., the expected agreement of the function from univariate degree-d polynomials over a randomly chosen line in $$\mathbb{F}_{q}^{m}$$, and prove that if this local agreement is $$\varepsilon\geq\Omega((d/q)^{\tau}))$$ for some fixed $$\tau > 0$$, then there is a global degree-d polynomial $$Q:\mathbb{F}_{q}^{m}\rightarrow \mathbb{F}_{q}$$ with agreement nearly $$\varepsilon$$ with $$f$$. This settles a long-standing open question in the area of low-degree testing, yielding an $O(d)$ -query robust test in the “high-error” regime (i.e., when $$\varepsilon < 1/2)$$. The previous results in this space either required $$\varepsilon > 1/2$$ (Polishchuk & Spielman, STOC 1994), or $$q=\Omega(d^{4})$$ (Arora & Sudan, Combinatorica 2003), orneeded to measure local distance on 2-dimensional “planes” rather than one-dimensional lines leading to $$\Omega(d^{2})$$ -query complexity (Raz & Safra, STOC 1997). Our analysis follows the spirit of most previous analyses in first analyzing the low-variable case $(m=O(1))$ and then “boot-strapping” to general multivariate settings. Our main technical novelty is a new analysis in the bivariate setting that exploits a previously known connection between multivariate factorization and finding (or testing) low-degree polynomials, in a non “black-box” manner. This connection was used roughly in a black-box manner in the work of Arora & Sudan — and we show that opening up this black box and making some delicate choices in the analysis leads to our essentially optimal analysis. A second contribution is a bootstrapping analysis which manages to lift analyses for $m=2$ directly to analyses for general $$m$$, where previous works needed to work with $m=3$ or $m=4$ — arguably this bootstrapping is significantly simpler than those in prior works. 

We prove that the most natural low-degree test for polynomials over finite fields is “robust” in the high-error regime for linear-sized fields. Specifically we consider the “local” agreement of a function $$f:\mathbb{F}_{q}^{m}\rightarrow \mathbb{F}_{q}$$ from the space of degree-d polynomials, i.e., the expected agreement of the function from univariate degree-d polynomials over a randomly chosen line in $$\mathbb{F}_{q}^{m}$$, and prove that if this local agreement is $$\varepsilon\geq\Omega((d/q)^{\tau}))$$ for some fixed $$\tau > 0$$, then there is a global degree-d polynomial $$Q:\mathbb{F}_{q}^{m}\rightarrow \mathbb{F}_{q}$$ with agreement nearly $$\varepsilon$$ with $$f$$. This settles a long-standing open question in the area of low-degree testing, yielding an $O(d)$ -query robust test in the “high-error” regime (i.e., when $$\varepsilon < 1/2)$$. The previous results in this space either required $$\varepsilon > 1/2$$ (Polishchuk & Spielman, STOC 1994), or $$q=\Omega(d^{4})$$ (Arora & Sudan, Combinatorica 2003), orneeded to measure local distance on 2-dimensional “planes” rather than one-dimensional lines leading to $$\Omega(d^{2})$$ -query complexity (Raz & Safra, STOC 1997). Our analysis follows the spirit of most previous analyses in first analyzing the low-variable case $(m=O(1))$ and then “boot-strapping” to general multivariate settings. Our main technical novelty is a new analysis in the bivariate setting that exploits a previously known connection between multivariate factorization and finding (or testing) low-degree polynomials, in a non “black-box” manner. This connection was used roughly in a black-box manner in the work of Arora & Sudan — and we show that opening up this black box and making some delicate choices in the analysis leads to our essentially optimal analysis. A second contribution is a bootstrapping analysis which manages to lift analyses for $m=2$ directly to analyses for general $$m$$, where previous works needed to work with $m=3$ or $m=4$ — arguably this bootstrapping is significantly simpler than those in prior works.